package com.example.algorithm.backtracing;

import java.util.*;

/**
 * 设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。
 *  这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。
 *  注意：本题相对原题做了扩展
 *
 *  示例:
 *   输入：4
 *  输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
 *   解释: 4 皇后问题存在如下两个不同的解法。
 * [
 * [".Q..", // 解法 1
 * "...Q",
 * "Q...",
 * "..Q."],
 *
 * ["..Q.", // 解法 2
 * "Q...",
 * "...Q",
 * ".Q.."]]
 */
public class Interview08_12_SolveNQueens {
    public static void main(String[] args) {

        List<List<String>> results = new Solution().solveNQueens(4);
        results.forEach(e -> {
            e.forEach(x -> {
                System.out.print(x);
                System.out.println();
            });
            System.out.println("\n\n");
        });

    }


    static class Solution {
        public List<List<String>> solveNQueens(int n) {
            return solveNQueens2(n);
        }

        /**
         * 解法二:回溯法(基于集合的回溯)
         *
         * 递归是一种算法结构，而回溯是一种算法思想，可以用递归实现
         * 从问题的某一种可能出发, 搜索从这种情况出发所能达到的所有可能,
         * 当这一条路走到“尽头”的时候, 再倒回出发点, 从另一个可能出发, 继续搜索。这就是回溯
         * 回溯就是一种试探，类似于穷举，但回溯有“剪枝”功能
         *
         * 思路:
         * 使用回溯探索可能情况，用集合记录每一列以及两个方向的每条斜线上的情况
         * 使用三个集合columns(HashSet), diagonals1(HashSet), diagonals2(HashSet)分别记录同一列以及两条斜线上是否皇后
         * @param n
         * @return
         */
        public List<List<String>> solveNQueens2(int n) {
            // 因为该问题有多个解,每个解是一个List<String>
            List<List<String>> results = new ArrayList<>();
            int[] queens = new int[n]; // queens[i] = m 表示i行的m列放置皇后
            Arrays.fill(queens, -1);// 初始化为-1
            Set<Integer> columns = new HashSet<>(); // columns.contains(i) 表示第i列上已经放置了皇后
            // 表示左上到右下的斜线，同⼀斜线上⾏列坐标之差相等，diagonals1.contains(i)表示某条斜线上已经放置了皇后
            Set<Integer> diagonals1 = new HashSet<>();
            Set<Integer> diagonals2 = new HashSet<>(); // 表示右上到左下的斜线，同⼀斜线上⾏列坐标之和相等,含义同diagonals1
            backtrack(results, queens, n, 0, columns, diagonals1, diagonals2);

            return results;
        }

        private void backtrack(List<List<String>> results, int[] queens, int n, int row,
                               Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
            if (row == queens.length) { // 递归出口
                List<String> res = generateSingleRes(queens);
                results.add(res);
                return;
            } else {
                for (int col = 0; col < n; col++) { // 在一行中从左到右一列一列尝试找到填充皇后的位置
                    if (columns.contains(col)) continue; // 当前列已经填充皇后则跳过，尝试下一列

                    int diagonal1 = row - col;// 使⽤用行列坐标之差来表示方向(左上到右下)的斜线
                    if (diagonals1.contains(diagonal1)) continue;
                    int diagonal2 = row + col;// 使⽤用⾏行行列列坐标只和来表示⽅方向⼆二(右上到左下)的斜线
                    if (diagonals2.contains(diagonal2)) continue;

                    // 记录可以填充皇后的位置并更新行列状态
                    queens[row] = col;
                    columns.add(col);
                    diagonals1.add(diagonal1);
                    diagonals2.add(diagonal2);

                    backtrack(results, queens, n, row + 1, columns, diagonals1, diagonals2); // 递归尝试求下一行

                    // 上⾯面的递归完成后，在(row,col)放置皇后对的前提下所有可能已经记录在results里⾯了，如果遇到能成功放置时要回溯回去
                    // 此时就需要复原状态
                    queens[row] = -1;
                    columns.remove(col);
                    diagonals1.remove(diagonal1);
                    diagonals2.remove(diagonal2);

                }
            }

        }

        public List<String> generateSingleRes(int[] queens) {
            List<String> board = new ArrayList<String>();
            for (int i = 0; i < queens.length; i++) {
                char[] rowStr = new char[queens.length];
                Arrays.fill(rowStr, '.'); // 先将一行全部填充成'.'
                rowStr[queens[i]] = 'Q'; // 将i行的queens[i]列放置皇后(置为'Q'即可)
                board.add(new String(rowStr));
            }
            return board;
        }

        /**
         * 解法一:递归(暴力法)
         * 从第一行第一列使用递归遍历所有可能
         * @param n
         * @return
         */
        public List<List<String>> solveNQueens1(int n) {
            // 初始化
            char[][] chess = new char[n][n];
            for (int i = 0; i < chess.length; i++) {
                for (int j = 0; j < chess[0].length; j++) {
                    chess[i][j] = '.';
                }
            }
            // 因为该问题有多个解,每个解是一个List<String>
            List<List<String>> results = new ArrayList<>();
            /// 从第一行开始从左到右递归尝试求出所有解
            solve(results, chess, 0);


            return results;
        }

        private void solve(List<List<String>> results, char[][] chess, int row) {
            if (row == chess.length) { // 递归出口
                // 访问完了最后一行,将递归所得到的的chess转化成一个res,并加入到结果集中
                List<String> res = generateSingleRes(chess);
                results.add(res);
            }

            for (int column = 0; column < chess.length; column++) { // 遍历每一列
                if (valid(chess, row, column)) { // 先判断当前位置能不能放置皇后
                    // 要copy是因为有可能本次的方案不满足所有行都能成功放置皇后,每次用副本来尝试不会修改原来的棋盘数据
                    char[][] copy = copy(chess);
                    copy[row][column] = 'Q';
                    solve(results, copy, row + 1); //递归判断下一⾏能不能成功放置皇后
                }

            }

        }

        private boolean valid(char[][] chess, int row, int column) {
            // 判断此列是否已经摆放过皇后(因为是从上到下遍历,所有此列下面不可能有摆放皇后的情况)
            for(int i = 0; i < row; i++) {
                if (chess[i][column] == 'Q') {
                    return false;
                }
            }
            // 不需要判断当前行是否有摆放皇后,因为本来就是一行只摆放一个皇后,在当前行遍历时当前行肯定还未摆放皇后

            //判断当前坐标的右上角有没有皇后
            for (int i = row - 1, j = column + 1; i >= 0 && j < chess.length; i--, j++) {
                if (chess[i][j] == 'Q') {
                    return false;
                }
            }
            //判断当前坐标的左上角有没有皇后
            for (int i = row - 1, j = column - 1; i >= 0 && j >= 0; i--, j--) {
                if (chess[i][j] == 'Q') {
                    return false;
                }
            }
            return true;

        }

        // 将棋盘转化成一个结果集
        private List<String> generateSingleRes(char[][] chess) {
            List<String> res = new ArrayList<>();
            for (int i = 0; i < chess.length; i++) {
                res.add(new String(chess[i]));
            }
            return res;
        }

        //把二维数组chess中的数据copy一份
        private char[][] copy(char[][] chess) {
            char[][] tmp = new char[chess.length][chess[0].length];
            for (int i = 0; i < chess.length; i++) {
                tmp[i] = chess[i].clone();
            }
            return tmp;
        }
    }
}
